package com.ly.algorithm.leetcode.BST;

/**
 * @Classname Problem94
 * @Description
 *
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 *
 * 假设一个二叉搜索树具有如下特征：
 *
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * 示例 1:
 *
 * 输入:
 *     2
 *    / \
 *   1   3
 * 输出: true
 * 示例 2:
 *
 * 输入:
 *     5
 *    / \
 *   1   4
 *      / \
 *     3   6
 * 输出: false
 * 解释: 输入为: [5,1,4,null,null,3,6]。
 *      根节点的值为 5 ，但是其右子节点值为 4 。
 *
 *
 * @Date 2020/12/22 22:01
 * @Author 冷心影翼
 */
public class Problem98 {

	public static void main(String[] args) {
		Solution98 solution98 = new Solution98();
		TreeNode treeNode = new TreeNode(1);
		treeNode.left = new TreeNode(2);
		treeNode.right = new TreeNode(4);
		System.out.println(solution98.isValidBST(treeNode));
	}
}

class Solution98 {
	public boolean isValidBST(TreeNode root) {
		return isValidBST(root,null,null);
	}

	public boolean isValidBST(TreeNode root,TreeNode min,TreeNode max) {
		if(root == null)
			return true;
		if((min!=null &&root.val <= min.val) || (max!=null && root.val >= max.val))
			return false;
		return isValidBST(root.left,min,root) && isValidBST(root.right,root,max);
	}
}